#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

struct ListNode 
{
	int val;
	struct ListNode* next;
};
typedef struct ListNode ListNode;

struct ListNode* insertionSortList(struct ListNode* head) 
{
	if (head == NULL)
	{
		return head;
	}
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	phead->val = 0;
	phead->next = head;
	ListNode* plast = head;
	ListNode* pcur = head->next;
	while (pcur != NULL)
	{
		if (plast->val <= pcur->val)
		{
			plast = plast->next;
		}
		else
		{
			ListNode* prev = phead;
			while (prev->next->val <= pcur->val)
			{
				prev = prev->next;
			}
			plast->next = pcur->next;
			pcur->next = prev->next;
			prev->next = pcur;
		}
		pcur = plast->next;
	}
	return phead->next;
}